package com.xy6.algo.greedy;

/**
 * 贪心法求解付款问题
 * 
 * <pre>
 * 假设有面值为5元、2元、1元、5角、2角、1角的货币，需要找给顾客x元y角现金， 求付出最少的货币数量。 
 * 如：4元6角，付出货币=2元+2元+5角+1角，min=4
 * 
 * 使用贪心法求解，结果可能不是最优。
 * 如果面值为3元、1元、8角、5角、1角，现金为4元6角，按照贪心法求解，结果为
 * 付出货币=3元+1元+5角+1角，min=4，实际最少为
 * 付出货币=3元+8角+8角，min=3。
 * 
 * 时间复杂度为：O(n)，n表示有n种不同面值的货币
 * 空间复杂度为：O(n)
 * 
 * <pre>
 * 
 * @author zhang
 * @since 2018-06-08
 */
public class Pay {

	public static void main(String[] args) {
		System.out.println(calc(4, 6));
	}

	/**
	 * 求解x元y角现金的最少货币数量
	 * 
	 * @param x
	 * @param y
	 * @return 货币数量
	 */
	public static int calc(int x, int y) {
		int[] units = { 50, 20, 10, 5, 2, 1 };
		int s = x * 10 + y;
		// 货币数量
		int n = 0;
		int len = units.length;
		for (int i = 0; i < len; i++) {
			int num = s / units[i];
			n += num;
			s = s % units[i];

			// 输出货币组成
			if (num > 0) {
				System.out.println(String.format("%d张%d角", num, units[i]));
			}
			// 兑齐，提前终止
			if (s == 0) {
				break;
			}
		}

		return n;
	}

	/**
	 * 贪心法的一般过程
	 * 
	 * @param x
	 * @param y
	 * @return
	 */
	public static int calc2(int x, int y) {
		// TODO 修改为更通用的写法
		// 候选集合
		int[] c = { 50, 20, 10, 5, 2, 1 };
		// 目标
		int t = x * 10 + y;
		// 初始化解集合。此处使用一个总金额表示
		int s = t;
		int i = 0;
		int n = 0;
		while (s > 0) {
			int a = select(c, i);
			i++;
			if (feasible(a, s, t)) {
				n += s / a;
				System.out.println(String.format("%d张%d角", s / a, a));
				s = s % a;
			}
			if (i >= c.length) {
				break;
			}
		}

		return n;
	}

	private static int select(int[] c, int index) {
		return c[index];
	}

	private static boolean feasible(int add, int s, int t) {
		if (s % add == 0) {
			return true;
		}
		return false;
	}

}
